package com.cjj.leetcoe.solution;

import java.util.HashMap;
import java.util.Map;

/**
 * @ClassName Solution_105
 * @Description 105. 从前序与中序遍历序列构造二叉树
 * @Date 2021/06/06 15:26:40
 * @Created by ccc-j
 * @email ccc-ju@outlook.com
 */
public class Solution_105 {
    Map<Integer, Integer> indexMap;

    /**
     * 解决思路：需要根据中序遍历中的下标去计算前序遍历中的下标，所以需要将中序遍历下标放入哈希表中
     * @param preorder
     * @param inorder
     * @return
     */
    public TreeNode buildTree(int[] preorder, int[] inorder){
        int n = preorder.length;
        indexMap  = new HashMap<Integer,Integer>();
        for(int i = 0; i < n; i++){
            indexMap.put(inorder[i], i);
        }
        return buildTree(preorder, 0, n - 1, inorder, 0, n - 1, indexMap);

    }

    private TreeNode buildTree(int[] preorder, int preLeft, int preRight, int[] inorder, int inLeft, int inRight, Map<Integer, Integer> indexMap) {
        // 递归终止条件
        if(preLeft > preRight || inLeft > inRight){
            return null;
        }
        // 找到根节点
        TreeNode root = new TreeNode(preorder[preLeft]);
        // 找到中序遍历的下标：pIndex
        int pIndex = indexMap.get(inorder[root.val]);
        /**
         * 前序遍历： 根   节   点   |    左     子     树     |      右      子      树
         *         preLeft         preLeft+1        x           x+1            preRight
         * 中序遍历   左      子      树     |    根节点       |      右      子       树
         *         inLeft        pIndex-1      pIndex           pIndex+1       inRight
         * x-(preLeft + 1) = pIndex - 1 - inLeft
         *               x = pIndex - inLeft + preLeft
         *               x + 1 = pIndex - inLeft + preLeft + 1
         */
        // 递归遍历左子树（需要寻找前序遍历左子树的边界和中序遍历的左子树的边界）
        root.left = buildTree(preorder, preLeft + 1, pIndex - inLeft + preLeft, inorder, inLeft, pIndex - 1, indexMap);
        // 递归遍历右子树（需要寻找前序遍历右子树的边界和中序遍历右子树的边界）
        root.right = buildTree(preorder, pIndex - inLeft + preLeft + 1, preRight, inorder, pIndex + 1, inRight, indexMap);
        return root;
    }
}
